package leetcode_400;

/**
 *@author 周杨
 *BurstBalloons_312_ 踩气球游戏 每次踩爆一个气球 获得其分数和左右两边的分数  问最高收益
 *describe:dp[left][right] =
 * max{dp[left][right] , nums[left] * nums[i] * nums[right]  + 
 *  nums[left] * nums[i]  +  
 *  nums[i] * nums[right]}; AC 53%
 *show:https://blog.csdn.net/swartz2015/article/details/50561199
 *2018年7月2日 下午3:44:38
 */
public class BurstBalloons_312_ {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	public int maxdps(int[] nums) {
		 int n = nums.length + 2;
	        int[] tmp = new int[n];
	        for (int i = 1; i < n - 1; i++) {
	            tmp[i] = nums[i - 1];
	        }
	        tmp[0] = tmp[n - 1] = 1;//重新定义数组
	        int[][] dp = new int[n][n];//dp[i][j]表示i-j中踩爆的最优解
	        // 动态规划过程：
	        int p = 0, q = 0;
	        for (int k = 1; k < n; k++) { // k 是间隔的队列长度
	            for (p = 0; p < n - k; p++) { // p　是队列头部
	                q = p + k; // q 队列尾部
	                for (int i = p + 1; i < q; i++) {
	                    dp[p][q] = Math.max(dp[p][q], dp[p][i] + dp[i][q] + tmp[p] * tmp[i] * tmp[q]);
	                }
	            }
	        }
	        return dp[0][n - 1];
        
    }
}
